package com.sort;

import java.util.Arrays;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: MergeSort
 * @description: 归并排序
 * @date 2021/2/815:09
 * @since V1.0
 */

public class MergeSort {
    public static void main(String[] args) {
        //        int[] arr = {5,42,78,11,37,894,131,-1};
        int[] arr = new int[8000000];
        for (int i=0;i<arr.length;i++){
            arr[i] = (int) (Math.random()*80000000);
        }
        long l = System.currentTimeMillis();
        int[] temp = new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
        //        System.out.println(Arrays.toString(arr));
        long l1 = System.currentTimeMillis();
        System.out.println((l1-l));
    }


    //分+合的方法
    public static  void mergeSort(int[] arr,int left,int right,int[] temp){
        //当left==right说明已经分到每一个元素了，已经递归到了最底层，进不去这个if,开始回溯
        if(left<right){
            int mid = (left+right)/2;
            //向左递归分解
            mergeSort(arr,left,mid,temp);
            //向右递归进行分解
            mergeSort(arr,mid+1,right,temp);
            //所以到合并时,最底层是[0,1][2,3][4,5]这样，最小单位是两个元素
            //合并
            merge(arr,left,mid,right,temp);
        }
    }


    /*合并数据的方法
     *
     * @Param: [arr, left, mid, right, temp]
     * 排序原数组，左边索引，中间索引，右边索引，中转数组
     * @Return: void
     * @Author: 江岸
     * @Date: 2021/2/8 15:38
     */
    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        //初始化左右指针
        int i=left;
        int j=mid+1;
        int t=0;
        //1.先把左右两边的数据按照规则充填到temp中
        while (i<=mid && j<=right){
            if (arr[i]<arr[j]){
                temp[t] = arr[i];
                i++;
                t++;
            }else {
                temp[t] = arr[j];
                j++;
                t++;
            }
        }
        //2.如果i或者j其中一边遍历完了，则把剩下的都移动到temp
        while(i<=mid){
            temp[t] = arr[i];
            i++;
            t++;
        }
        while (j<=right){
            temp[t] = arr[j];
            j++;
            t++;
        }
        //3.把temp拷贝回arr，并不是每次都拷贝所有的
        t = 0;
        int templeft = left;
        while (templeft<=right){
            arr[templeft] = temp[t];
            t++;
            templeft++;
        }
    }
}
